#include <iostream>
#include <vector>

using namespace std;

class Solution 
{
public:
	vector<int> searchRange(vector<int>& nums, int target) 
	{
		int leftIndex = findLeftBorder(nums, target);
		int rightIndex = findRightBorder(nums, target);
		
		// 如果左边界或右边界未找到，说明 target 不存在
		if (leftIndex == -1 || rightIndex == -1) 
		{
			return {-1, -1};
		}
		else
		{
			return {leftIndex, rightIndex};	
		}
	}
	
private:
	// 查找 target 的左边界（第一个出现的位置）
	int findLeftBorder(vector<int>& nums, int target) 
	{
		int left = 0;
		int right = nums.size() - 1;
		int leftBorder = -1;
		
		while (left <= right) 
		{
			int mid = left + (right - left) / 2;
			
			if (target == nums[mid]) 
			{
				leftBorder = mid; // 记录左边界
				right = mid - 1;  // 继续向左查找
			}
			else if (target < nums[mid]) 
			{
				right = mid - 1;  // 目标值更小，往左找
			}
			else 
			{
				left = mid + 1;  // 目标值更大，往右找
			}
		}
		
		return leftBorder;
	}
	
	// 查找 target 的右边界（最后一个出现的位置）
	int findRightBorder(vector<int>& nums, int target) 
	{
		int left = 0;
		int right = nums.size() - 1;
		int rightBorder = -1;
		
		while (left <= right) 
		{
			int mid = left + (right - left) / 2;
			
			if (target == nums[mid]) 
			{
				rightBorder = mid; // 记录右边界
				left = mid + 1;    // 继续向右查找
			}
			else if (target < nums[mid]) 
			{
				right = mid - 1;  // 目标值更小，往左找
			}
			else 
			{
				left = mid + 1;  // 目标值更大，往右找
			}
		}
		
		return rightBorder;
	}
};

int main() 
{
	Solution sol;
	vector<int> nums = {5, 7, 7, 8, 8, 10};
	int target;
	
	cout << "请输入目标值: ";
	cin >> target;
	
	vector<int> result = sol.searchRange(nums, target);
	cout << "[" << result[0] << ", " << result[1] << "]" << endl;
	
	return 0;
}





